package com.chenken;

/**
 *	冒泡排序
 *	用前一个元素与后一个元素比较，如果前一个元素较大，将2个元素交换位置
 *  每进行一轮，数组中的最大元素都会被挑选出来，放到最后，
 *  所以，每进行一轮，最后面的元素都不需要扫描，外层循环要i--
 *  
 */
public class BubbleSort3<T extends Comparable<T>> extends Sort<T>{
	
	/**
	 * 如果序列尾部已经局部有序，可以记录最后一次交换的位置，较少比较次数
	 *  最坏，平均时间复杂度O(n^2)
	 *	最好，平均时间复杂度O(n)
	 * 	空间复杂度O(1)
	 */
	@Override
	public void sort() {
		for(int end = arrays.length-1;end>0;end--) {
			int sortIndex = 0;
			for(int begin = 1;begin<=end;begin++) {
				if(compare(arrays[begin],arrays[begin-1])<0) {
					swap(begin,begin-1);
					sortIndex = begin;//记录这一轮最后一次交换的位置
				}
			}
			end = sortIndex;
		}
	}
}
